package other._1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.function.BiConsumer;

/**
 * @author mazouri
 * @create 2022-01-03 20:23
 */
public class ConvexHull {
    List<Line> lines = new ArrayList<>();//点集pts的凸包

    public List<Line> handle(List<Point> pts) {
        lines.clear();
        if (pts == null) {
            return lines;
        }
        int n = pts.size();
        double a, b, c, cc, l, r;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {//穷举点集中任意两点组成的直线ax+by=c
                a = pts.get(j).y - pts.get(i).y;//
                b = pts.get(i).x - pts.get(j).x;
                c = pts.get(i).x * pts.get(j).y - pts.get(i).y * pts.get(j).x;
                l = r = 0;
                int k;
                for (k = 0; k < n; k++) {//穷举点集中的每一点
                    cc = a * pts.get(k).x + b * pts.get(k).y;
                    if (cc > c) l++;
                    else if (cc < c) r++;
                    if (l * r != 0) break;//直线两侧都有点,
                }
                if (k == n) {//凸包中添加一条边
                    lines.add(new Line(pts.get(i), pts.get(j)));
                }
            }
        }
        return lines;
    }

    public static void main(String[] args) {
        int baseNum = 100;
        for (int i = 0; i < 8; i++) {
            List<Point> points = Client.generatePoint(baseNum);
            long begin = System.currentTimeMillis();
            new ConvexHull().handle(points);
            long end = System.currentTimeMillis();
            System.out.println(baseNum+"     "+ (end-begin));
            baseNum*=10;
        }
    }
}


